#include <stdlib.h>
#include <stdio.h>

// 弗洛伊德算法(Floyd)，求最短路径

typedef char VertexType; // 顶点数据类型
typedef int EdgeType;  // 边的权值类型
#define MAXVEX 100       // 最大顶点数
#define MAXEDGES 200     // 最大边数
#define MAX 0x10000   // 无穷大

typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;

void createGraph(Graph *G){
    G->numVertexes = 9;
    G->numEdges = 16;
    // 初始化邻接矩阵
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';

    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            if (i == j){                  
                G->arc[i][j] = 0;  // 对角线为0
            } else {
                G->arc[i][j] = MAX; // 用无穷大表示不连通
            }
        }
    }

    // 建立边(权值)
    //  
    G->arc[0][1] = 1;
    G->arc[0][2] = 5;

    G->arc[1][2] = 3;  
    G->arc[1][3] = 7;
    G->arc[1][4] = 5;

    G->arc[2][3] = 1;
    G->arc[2][4] = 7;

    G->arc[3][4] = 2;
    G->arc[3][6] = 3;

    G->arc[4][5] = 3;
    G->arc[4][6] = 6;
    G->arc[4][7] = 9;

    G->arc[5][7] = 5;

    G->arc[6][7] = 2;
    G->arc[6][8] = 7;

    G->arc[7][8] = 4;

    for (int i = 0; i < G->numVertexes; i++){
        for (int j = 0; j < G->numVertexes; j++){
            G->arc[j][i] = G->arc[i][j]; // 无向图邻接矩阵对称
        }
    }
}


void floyd(Graph G){
    int path[MAXVEX][MAXVEX]; // 路径数组
    int dist[MAXVEX][MAXVEX]; // 距离数组

    for (int i = 0; i < G.numVertexes; i++){
        for (int j = 0; j < G.numVertexes; j++){
            dist[i][j] = G.arc[i][j]; // 初始化距离数组
            path[i][j] = j;          // 初始化路径数组
        }
    }

    // 核心算法
    // j:起始顶点 i:中间顶点 k:终点
    for (int i = 0; i < G.numVertexes; i++){         // 中间顶点
        for (int j = 0; j < G.numVertexes; j++){     // 起点
            for (int k = 0; k < G.numVertexes; k++){ // 终点
                if (dist[j][i] + dist[i][k] < dist[j][k]){ // 如果经过k顶点距离更短
                    dist[j][k] = dist[j][i] + dist[i][k]; // 更新距离数组
                    path[j][k] = path[j][i]; // 更新路径数组，记录经过的顶点
                }
            }   
        }
    }

    // 输出结果
    int k;
    for(int i = 0; i < G.numVertexes; i++){
        for (int j = i+1; j < G.numVertexes; j++){
            printf("v%d(%c)-->v%d(%c): ", i, G.vexs[i], j, G.vexs[j]);
            k = path[i][j];
            printf("dist=%d ", dist[i][j]);
            printf("path=%c", G.vexs[i]);
            while (k != j){ // 输出路径
                printf("->%c", G.vexs[k]);
                k = path[k][j];
            }
            printf("->%c\n", G.vexs[j]);
        }
    }
}

int main(){
    Graph G;
    createGraph(&G);
    floyd(G);
    return 0;
}